package com.wfm.common;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class ArrayUtils {

    /**
     * ===================打印二维数组=======================
     * @param num
     */
    public static void printTwoNum(int[][] num){
        for (int i = 0; i < num.length; i++) {
            System.out.println(Arrays.toString(num[i]));
        }
    }

    /**
     * =============================堆排序
     * @param nums
     */
    public static void heapSort(int[] nums){
        int len = nums.length;
        buildMaxHeap(nums,len);
        for (int i = len-1; i >=1 ; i--) {
            swap(nums,i,0);
            len=len-1;
            maxHeapify(nums,0,len);
        }
    }

    /**
     * ===============================构建大顶堆=============
     * @param a
     * @param heapSize
     */
    public static void buildMaxHeap(int[] a, int heapSize) {
        // 完全二叉树中，树元素个数的一半向下取整再-1，得到的是最后一个非叶节点
        for (int i = heapSize / 2 -1; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }
    public static void maxHeapify(int[] a, int i, int heapSize) {
        // l是树左孩子，r树右孩子，largest标记父左右三个里的最大值，默认largest指向父
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        // 如果左孩子比父大，把largest指向左孩子
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        // 如果右孩子比最大的还大，标记largest指向右孩子
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        // 如果largest标记的和最初默认指定的父不一样，也就是子中存在大于父的，则上浮
        // 然后递归处理下浮后的那个节点树
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /**
     * =========================快速排序======================
     * @param nums
     * @param left 闭区间
     * @param right 闭区间
     */
    public static void quickSort(int[] nums,int left,int right){
        if(left<right){
            int partition = partition(nums, left, right);
            quickSort(nums,left,partition-1);
            quickSort(nums,partition+1,right);
        }
    }

    /**
     * 也是闭区间，
     * 区别是：和下面相比，省去了swap，因为前面保存了pivot，所以num[left]就是一个可以被
     * 覆盖的地方，所以你发现第一个while需要先从右边开始，然后再把nums[right]->nums[left];
     * 其实还可以
     * 把            while (left<right&&nums[right]>=pivot){
     *                 right--;
     *             }
     * 简写
     *             while (left<right&&nums[right--]>=pivot)；
     * 如果 while (left<right&&nums[--right]>=pivot)；就变成了左闭右开区间
     */
    public static int partition(int[] nums,int left,int right){
        int pivot = nums[left];
        while (left!=right){
            while (left<right&&nums[right]>=pivot){
                right--;
            }
            nums[left]=nums[right];
            while (left<right&&nums[left]<=pivot){
                left++;
            }
            nums[right]=nums[left];
        }
        return left;
    }

    /**
     * 也是闭区间
     * 需要swap
     */
    public static int partition2(int[] nums,int left,int right){
        int pivot = nums[left];
        while (left!=right){
            while (left<right&&nums[left]<pivot){
                left++;
            }
            while (left<right&&nums[right]>pivot){
                right--;
            }
            swap(nums,left,right);
        }
        return left;
    }

    /**
     * 防止left就是最终位置， int pivot = nums[left];
     * 所以随机一下
     */
    public int randomPartition(int[] a, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(a, l, i);
        return partition(a, l, r);
    }

    /**
     * ====================================快速查找================
     * 找到第k小的数  1 2 3 4 5  如果k=3，则return 3
     *
     */
    public static int quickSelect(int[] nums,int left,int right,int k){
        int ans = -1;
        if(left<right){
            int partition = partition(nums, left, right);
            int i = partition-left+1;
            if(i==k){
                return nums[i];
            }else if(k<i){
                ans = quickSelect(nums,left,partition-1,k);
            }else {
                ans = quickSelect(nums,partition+1,right,k);
            }
        }
        return ans;
    }


    /**
     * =====================================分治排序
     * @param nums
     * @param left 闭区间
     * @param right 闭区间
     */
    public static void mergeSort(int[] nums,int left,int right){
        if(left<right){
            int mid = (left+right)>>1;
            mergeSort(nums,left,mid);
            mergeSort(nums,mid+1,right);
            merge(nums,left,mid,right);
        }
    }

    public static void merge(int[] nums,int left,int mid ,int right){
        int length = right-left+1;
        int[] tmp = new int[length];
        int _left = left;
        int _right = mid+1;
        int index = 0;
        while (_left<=mid&&_right<=right){
            if(nums[_left]<nums[_right]){
                tmp[index++]=nums[_left++];
            }else {
                tmp[index++] = nums[_right++];
            }
        }
        while (_left<=mid){
            tmp[index++]=nums[_left++];
        }
        while (_right<=right){
            tmp[index++]=nums[_right++];
        }
        for (int i = 0; i < tmp.length; i++) {
            nums[left+i]=tmp[i];
        }
    }


    /**
     * =====================================二分查找
     */
    public static int binSearch(int[] nums,int left,int right,int target){
        while (left<=right){
            int m = left+(right-left)/2;
            if(target<nums[m]){
                right=m-1;
            }else if (nums[m]<target){
                left=m+1;
            }else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找 1 2 4 4 5   4
     * return 2
     */
    public static int binSearchLeft(int[] nums,int left,int right,int target){
        int ans = -1;
        while (left<=right){
            int m = left+(right-left)/2;
            if(target<nums[m]){
//                ans = m;   // 找到插入位置
                right=m-1;
            }else if (nums[m]<target){
                left=m+1;
            }else {
                ans = m;
                right = m-1; // 相同靠左
            }
        }
        return ans;
    }

    public static int binSearchRight(int[] nums,int left,int right,int target){
        int ans = -1;
        while (left<=right){
            int m = left+(right-left)/2;
            if(target<nums[m]){
//                ans = m;   // 找到插入位置
                right=m-1;
            }else if (nums[m]<target){
                left=m+1;
            }else {
                ans = m;
                left = m+1;  // 相同靠右
            }
        }
        return ans;
    }
}
